package sortAlgorithm.quickSort;

import java.util.Arrays;

/**
 * @author： pang-yun
 * @date： 2021-10-08 10:39
 * 功能目的 ：用于 快速排序   by myself
 */

public class QuickSortPro {
    public static void main(String[] args) {
        int[] arr= new int[]{10,9,8,7,6,5,4,3,2,1};
        sort(arr,0,9);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr,int low, int high) {
        if (high<low)   return;
        int partition = partition(arr, low, high);

        sort(arr,low,partition-1);
        sort(arr,partition+1,high);

    }

    public static int partition(int[] arr,int low, int high){
        int key= arr[low];
        int left=low+1;
        int right=high;
        int temp =0;

        while (true){
            // 从右向左找到 小于 key的 值
            while (arr[right]>key){
                right--;
                // 如果已经达到数组边界  跳出
                if (right==low)break;
            }
            // 从左向右寻找 一个比 key  大的值
            while (arr[left]<key){
                left++;
                // 如果 已经达到数组边界 跳出
                if (left==high)break;
            }
            // 如果 left > right   说明整体已经 排序 完毕   跳出   否则进行交换之后 继续排序
            if (left>=right){break;}else {
                temp=arr[right];
                arr[right]=arr[left];
                arr[left]=temp;
            }
        }
        // 排序完毕之后将 必须是 right 与 中间交换
        // right 停下时 确保 其值 是小于 arr[low], 并且right右边全部大于 arr[low]  交换之后  右边全部大于 arr[low] 左边全部小于 arr[low]
        temp=arr[low];
        arr[low]=arr[right];
        arr[right]=temp;
        return right;
    }

}
